package zuo.test7_prefixTree;

/**
 * @Author: Forx
 * @Data: 2021/6/16
 * @Desc: Algorithm - zuo.test7_prefixTree
 * @Version: v1.0
 */
public class prefixTree {
    public static class TrieNode {
        public int pass;
        public int end;
        public TrieNode[] nexts;

        public TrieNode() {
            pass =0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }
    public static class Trie{
        private TrieNode root;
        public Trie(){
            root = new TrieNode();
        }

        public void  insert(String word){
            TrieNode node = this.root;
            node.pass++;
            char[] chars = word.toCharArray();
            int index = 0;
            for(char c:chars){
                index = c-'a';
                if(node.nexts[index]==null){
                    node.nexts[index] = new TrieNode();
                }
               node = node.nexts[index];
                node.pass++;
            }
            node.end++;
        }
        public void delete(String word){
            if(search(word)!=0){
                TrieNode node = this.root;
                char[] chars = word.toCharArray();
                node.pass--;
                int index = 0;
                for(char c : chars){
                    index = c-'a';
                    if(--node.nexts[index].pass == 0){
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }



        }
        public int search(String word){
            if(word==null)return 0;
            char[] chars = word.toCharArray();
            TrieNode node = this.root;
            int index = 0;
            for(char c:chars){
                index = c-'a';
                if(node.nexts[index]==null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;

        }
        public int prefixNum(String word){
            if(word==null)return 0;
            char[] chars = word.toCharArray();
            TrieNode node = this.root;
            int index = 0;
            for(char c:chars){
                index = c-'a';
                if(node.nexts[index]==null){
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }


    }




}
